COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00022 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a48.tex[106,phy] \today\hfill}

\bigskip
\line{{\bf Pascal Functions and Procedures.} (Assumes type definition, blocks.)
\hfil}

Pascal embodies several ways of incorporating subalgorithms into programs.
Subalgorithms that compute a single value are best expressed as {\sl functions\/}
in Pascal, while subalgorithms that compute several values (or none) are
best expressed as Pascal {\sl procedures\/}.  
Before describing these subalgorithms
in their full generality, I will first describe restricted forms that lend 
themselves to disciplined programming: {\sl pure\/} functions and procedures.

A pure function in Pascal is a subalgorithm that takes a fixed number of
input values (each required to be of a specified type), carries out a
computation that interacts with its master algorithm only through inspection
of the input values, and returns to the master algorithm [RWF: define]
a single value of a
specified type.

Here is an example of a Pascal function definition:

{\obeylines\obeyspaces\let =\ \tt
        FUNCTION H (A:INTEGER;B:INTEGER):REAL;
        VAR I:INTEGER;S:REAL;
        BEGIN
        S:=0.0;
        FOR I:=A TO B DO
            S:=S+1/I;
        H:=S
        END
}

\noindent
This function is a subalgorithm which is executed after values have been given
to $A$ and~$B$; it adds ${1\over A}, {1\over A+1}, {1\over A+2},\ldots, 
{1\over B}$,
and returns the sum to the master program.

The general form of a pure function definition is

\figbox 2truein:

Within the block, the parameters (e.g., $A$ and $B$) 
are used like storage variables [RWF: define].
The name of the function (e.g.,~$H$) is used within the function block as a result
variable, to which an assignment must be made before completion of the block.

************** Define blocks

In a pure 
function, no use is made of variables or parameters other than those
belonging to the function itself.  This implies that information enters the
function only through parameters, and leaves only through the result variable.

A function definition appears in the subprogram declaration section of its
master program.  The defined function may be used in the block of its master
program, and also in any subprogram  definitions that follow it in the same
subprogram declaration section. [RWF: depends on section on scope rules?]

Pascal functions are used in expressions, in much the same way that builtin
functions like {\tt COS} and {\tt ABS} are used.  
If $F$ is the name of the function, and
$E↓1,E↓2,\ldots,E↓n$ are expressions for its arguments (input values), then
$F(E↓1,E↓2,\ldots,E↓n)$ is a {\it function call\/}, 
an expression whose value is found by
executing the function.  The arguments must be assignable to the corresponding
parameters of the function; ordinarily this means the types are the same.
The function is executed by evaluating the arguments, assigning their respective
values to the parameters, and executing the body of the function.  The function
body must assign a value to its result variable.  When it finishes, the value
of its result variable is taken as the value of the function call.

The use of functional notation for function calls makes it easy to use 
the result of
one function call as an argument to another.  To evaluate $g(x,y)$ with result~$r$,
and then to evaluate $f(z,r)$, requires only writing the expression 
$f\bigl(z,g(x,y)\bigr)$;
the intermediate result does not have to be given a name (like~$r$) in the program.

To trace the action of a function call, we draw a new contour.  Suppose the above
function~{\tt H} is called in the context

{\obeylines\obeyspaces\let =\ \tt
        WRITE(H(P,Q-1)/(P-Q))
}

\noindent
with ${\tt P}=2$, ${\tt Q}=5$.  First we evaluate the
arguments, ${\tt P}= 2$, ${\tt Q}-1 = 4$.  We write down the function call with the
constant arguments

{\obeylines\obeyspaces\let =\ \tt
        H(2,4)
}

\noindent
and open a contour box, with the arguments assigned to
the parameters (${\tt A}=2$, ${\tt B}=4$), the ordinary variables of the function 
undefined (${\tt I}=?$, ${\tt S}=?$) and the result variable undefined 
(${\tt H}=?$).

\vfill\eject

We now have

{\obeylines\obeyspaces\let =\ \tt
        H(2,4)

        A=2
        B=4
        I=?
        S=?
        H=?
}

\noindent
and proceed to execute the function.

{\obeylines\obeyspaces\let =\ \tt
        S:=0.0
        S=0.0
            FOR I:=2 TO 4

        I=2
            S:=0.0+ 1/2
            S=0.5

        I=3
            S:=0.5+1/3
            S=0.83

        I=4
            S:=0.83+1/4
            S=1.07

        I=5

        I=?

        H:=1.07

        H=1.07

        H(2,4)=1.07
}

\smallskip
When finished, we close the contour box, and copy the value of the result variable,
as shown above.  We then continue in the master algorithm, using that result as
the value of the function call:

{\obeylines\obeyspaces\let =\ \tt
        WRITE(1.07/(5-2))                0.36
}

\bigskip
\noindent
A function may be a subprogram to the main program, but it may also be a
subprogram to another subprogram.  If function  $F$  is a subprogram of of 
function~$G$, its definition appears in the subprogram declarations section of the
block in the definition of~$G$.

What we have described as a pure function interacts with its master program
only through its parameters and result variable.  Other kinds of interaction
are allowed by Pascal, as we shall see later, but for 
ninety percent
of the applications
of functions, a pure function is most satisfactory.  In particular, it is easier
to understand and debug programs that use only pure functions.

Subprograms with exactly one result are readily designed as Pascal functions.
Subprograms with no results, or with several, are better designed as 
{\sl procedures\/}.
The principal difference is that a call on a function is an expression that
executes the function and stands for the result; a call on a procedure is a
statement, which executes the procedure, but does not stand for a result.


\vfill\eject

Here is an example of a Pascal procedure, with no result.

{\obeylines\obeyspaces\let =\ \tt
        PROCEDURE SQUARE (N:INTEGER;C:CHAR);
        VAR I,J:INTEGER;
        BEGIN
        WRITELN;
        FOR I:=1 TO N DO
            BEGIN
            FOR J:=1 TO N DO
                WRITE(C);
            WRITELN
            END
        END;
}

This procedure is a subalgorithm that is executed after values have been given
to $N$ and~$C$; it prints an $N\times N$ square of the 
character~$C$, and then returns to
the master program.  A~call {\tt SQUARE(4,'*')} would print

\smallskip
{\baselineskip5pt
{\obeylines\obeyspaces\let =\ \tt
        ****
        ****
        ****
        ****
}
}

\smallskip
If a parameter or set of parameters of a procedure or function is preceded by
the word {\tt VAR}, the parameters are variables; the subprogram may, by assigning
values to them, assign those values to the corresponding arguments in the
master program.  Arguments corresponding to variable parameters must be variables.
Here is an example procedure to find both roots of an equation  $AX↑2+BX+C=0$,

{\obeylines\obeyspaces\let =\ \tt
        PROCEDURE QUADRATIC (A,B,C:REAL;VAR ROOT1,ROOT2:R REAL);
            VAR D;
            BEGIN
            D:=SQRT(B*B-4*A*C);
            ROOT1:= (-B+D)/(2*A);
            ROOT2:= (-B-D)/(2*A)
            END
}

\noindent
The call {\tt QUADRATIC(2,-3,1,X,Y)}
followed by {\tt WRITE(X,Y)}
will print [FILL IN].


\vfill\eject

The general form of a pure procedure definition is

\figbox 3truein:

Within the block, the parameters are used like storage variables.  Variable
parameters are not distinct from their arguments; an assignment to a variable
parameter is an assignment to the argument variable.  This is the way to return
results to the master algorithm.  In a pure procedure, no use is made of
variables or parameters other than those belonging to the function itself.
This implies that information enters the procedure only through parameters,
and leaves only through variable parameters. [RWF: Add restrictions on uses
of parameters.]

A pure function is very easy to test separately from the rest of the program.
If it works with numbers as arguments, we can try it with constant arguments 
{\tt C1,C2,...,Cn} by incorporating the function definition in this program:

{\obeylines\obeyspaces\let =\ \tt
        PROGRAM....(OUTPUT);
        definition of function F;
            BEGIN
            WRITELN(C1,C2,...,Cn,F(C1,C2,...,Cn))
            END.
}

The penultimate line can be repeated with as many different argument values as
needed, or one can iterate:

{\obeylines\obeyspaces\let =\ \tt
        FOR I:= 1 TO TESTSIZE DO
            BEGIN
            READ(X1,X2,...,XN);
            WRITELN(X1,X2,...,XN,F(X1,X2,...,XN)
            END
}

\noindent
Such a program is called a 
driver [defined earlier?]; its only purpose is to test a pure function on
data for which the correct result is known.

%\vfill\eject

Conversely, it is easy to test the main program without the correct definition of
the pure function, replacing the function's definition by some easy function.
If the main program is designed to form the sum $F(1)+F(2)+\cdots +F(100)$, and the
correct definition of $F$ is difficult to program, we can test the summation and 
the printing format by using the easy function $F(X)=X$, this way:

{\obeylines\obeyspaces\let =\ \tt
        PROGRAM P(OUTPUT);
        VAR J:INTEGER;SUM:REAL;
        FUNCTION F(I:INTEGER):REAL;
            BEGIN
            F:=I
            END;
        BEGIN
        SUM:=0.0
        FOR J:=1 TO 100 DO
            SUM:=SUM+F(J);
        WRITELN(SUM:8:2)
        END.
}

If the program prints 5050.00, we know that the main program is in good shape.
We have tested it using a {\sl stub\/} 
in place of the correct subprogram; a stub goes
through the same motions [CLARIFY]
as the absent subprogram, without necessarily giving
correct answers.

If the test of the master program requires that the subprogram give correct
answers, we can still test with a stub, but the stub now asks the user for help.
The declaration of the stub looks like: [depends on {\tt FILES} section]

{\obeylines\obeyspaces\let =\ \tt
        FUNCTION F(X,Y:REAL):REAL;
        BEGIN
        WRITELNSCREEN('WHAT IS F IF X AND Y ARE',X,Y,'?');
        READKEYS(F);
        END
}

Every part of a program under development can be tested separately, by using a
driver to substitute for its master program, and stubs to substitute for its
subprograms.  This technique allows a team to subdivide a programming project
in such a way that no bottlenecks impede the testing.

\line{Reference:  Aron, {\sl The Program Development Process\/}.\hfill}





\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft October 16, 1984

\vfill\eject

$$\vcenter{\baselineskip0pt
\halign{\hfil #\hfil%
&$\hfil #\hfil$\qquad%
&#\hfil%
&\quad\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\qquad%
&#\hfil%
&#\hfil\qquad%
&#\hfil\qquad%
&#\hfil\cr
&&function&&&&result\cr
FUNCTION&&name =&&&:&type =&;&block&;\cr
&&identifier&&&&identifier\cr
\noalign{\bigskip\bigskip}
&&\hfill (&&&)\cr
&&&;\cr
\noalign{\bigskip}
&&&&&&¶meter\cr
&&\qquad parameter =&&&&:&type =\cr
&&\qquad identifier&&&&&identifier\cr
\noalign{\bigskip}
&&&&,\cr
}}$$


\bigskip
\bigskip
\bigskip
\bigskip

$$\vcenter{\baselineskip0pt
\halign{\hfil#\hfil%
&#\hfil%
&#\hfil%
&#\hfil%
&#\hfil\quad%
&#\hfil\quad%
&#\hfil\quad%
&#\hfil%
&#\hfil\cr
&&procedure\cr
PROCEDURE&&name =&&&;&&block&;\cr
&&identifier\cr
&&&\hfill (&&)\cr
\noalign{\smallskip}
&&&&;\cr
\noalign{\bigskip}
&VAR&\quad$\bullet$¶meter =&&$\bullet$&:&type name =\cr
&&&identifier&&&&identifier\cr
\noalign{\smallskip}
&&&&&,\cr
}}$$

\bye